package com.mlamp.单调栈;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class 下一个最大值 {
    public static void main(String[] args) {
        int[] result = new int[]{
                2, 1, 2, 4, 3
        };
        int[] ints1 = nextGreaterNumber(result);
        System.out.println(Arrays.toString(ints1));
        System.out.println(Arrays.toString(nextGreaterNumber1(result)));
        System.out.println(Arrays.toString(nextGreaterNumber22(result)));
        int warmdays[] = new int[]{73, 74, 75, 71, 69, 76};
        int[] ints = nextWarmDay(warmdays);
        System.out.println(Arrays.toString(ints));
        System.out.println(Arrays.toString(nextWarmDay3(warmdays)));


    }


    private static int[] nextGreaterNumbers(int[] inputs) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[inputs.length];
        for (int i = inputs.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= inputs[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(inputs[i]);
        }
        return res;
    }


    private static int[] nextGreaterNumber22(int[] inputs) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[inputs.length];
        for (int i = inputs.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= inputs[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(inputs[i]);
        }
        return res;
    }


    private static int[] nextGreaterNumber3(int[] ints) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[ints.length];
        for (int i = result.length; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= ints[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(ints[i]);
        }
        return result;
    }


    private static int[] nextGreaterNumber1(int[] ints) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[ints.length];
        for (int i = result.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= ints[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(ints[i]);
        }
        return result;
    }


    private static int[] nextGreaterNumber(int[] ints) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] result = new int[ints.length];

        //[2,1,2,4,3]
        for (int i = ints.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peekLast() <= ints[i]) {
                stack.pollLast();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peekLast();
            stack.offer(ints[i]);
        }
        return result;
    }


    private static int[] nextWarmDay1(int[] ints) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[ints.length];
        for (int i = result.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && ints[stack.peekLast()] <= ints[i]) {
                stack.pollLast();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peekLast() - 1;
            stack.offer(i);
        }
        return result;
    }


    private static int[] nextWarmDay3(int[] inputs) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[inputs.length];
        for (int i = inputs.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && inputs[stack.peek()] <= inputs[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return result;
    }


    private static int[] nextWarmDay2(int[] ints) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] result = new int[ints.length];
        for (int i = ints.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && ints[stack.peek()] <= ints[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return result;
    }


    private static int[] nextWarmDay(int[] ints) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int[] result = new int[ints.length];

        //[2,1,2,4,3]
        for (int i = ints.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && ints[stack.peekLast()] <= ints[i]) {
                stack.pollLast();
            }
            result[i] = stack.isEmpty() ? 0 : (stack.peekLast() - i);
            stack.offer(i);
        }
        return result;
    }

}
